Nguyễn Tùng Cương sinh ngày 4 tháng 10 năm 1919 tại Giáo xứ Bút Đông, Giáo hạt Hà Nam, Tổng giáo phận Hà Nội, có địa chỉ hành chính thuộc thôn Đông Nội, xã Châu Giang, huyện Duy Tiên (nay là phường Châu Giang, thị xã Duy Tiên), tỉnh Hà Nam.[4] Thân phụ ông là ông Tín, giáo dân thường gọi là cụ cố Tín.

Năm 1931, cậu bé Nguyễn Tùng Cương bắt đầu đi theo con đường tu học.[5] Sau quá trình tu học, ông được truyền chức linh mục 3 tháng 12 năm 1949 tại Hà Nội[4] do Giám mục Jean Marie Mazé Kim chủ phong. Sau khi được truyền chức, linh mục Cương được bổ nhiệm đảm trách vai trò Phó xứ Hàm Long, Hà Nội từ năm 1950. Hai năm sau đó, ông trở thành linh mục chính xứ Hàm Long, kiêm linh mục Hạt trưởng Hạt Vĩnh Trị, Nam Định. Từ ngày 6 tháng 6 năm 1954, Nguyễn Tùng Cương đảm trách vai trò linh mục Quản lý Nhà chung Hà Nội.[5]

Trong cương vị quản lý nhà chung, linh mục Nguyễn Tùng Cương nhiều lần bị triệu tập làm việc với chính quyền, có khi liên tục 21 ngày đêm. Sau mỗi lần làm việc, linh mục Cương trở nên xanh xao và phờ phạc. Giám mục Phanxicô Xaviê Nguyễn Văn Sang nhận định linh mục Nguyễn Tung Cương bị tra tấn về tinh thần. Sau mỗi lần kết thúc triệu tập, linh mục Cương thường đi xe máy đến cử hành thánh lễ tại giáo xứ Kẻ Sét.[6]

Nguyễn Tùng Cương có nghĩa tử là Giuse Nguyễn Văn Yến, sau là Giám mục chính tòa Giáo phận Phát Diệm.[7]